package main.leetcode.clockin.April;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 46.全排列
 *
 * <p>给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 *
 * <p>示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day25 {
    public static void main(String[] args) {
        System.out.println(new day25().permute(new int[] {1, 1, 2, 2}));
        //        System.out.println(new day25().permute(new int[] {1, 1, 3}));
    }

    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        dfs(list, res, 0, n);
        return res;
    }

    private void dfs(List<Integer> list, List<List<Integer>> res, int i, int n) {
        if (i == n) {
            res.add(new ArrayList<>(list));
            return;
        }
        for (int j = i; j < n; ++j) {
            // 在i至j间存在重复的数，则continue，只对排在最后的重复值进行交换
            if (!isRepeated(i, j, list)) {
                Collections.swap(list, i, j);
                dfs(list, res, i + 1, n);
                Collections.swap(list, i, j);
            }
        }
    }

    private boolean isRepeated(int i, int j, List<Integer> list) {
        int tmp = list.get(j);
        for (int k = i; k < j; ++k) {
            if (list.get(k) == tmp) {
                return true;
            }
        }
        return false;
    }
}
